#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct HufumanTreeNode{
    int parent;
    int Lchild;
    int Rchild;
    int Weight;
}HufumanTreeNode;
typedef struct HufumanTreeNode * HuffmanTree;
typedef char ** HuffmanCode;

int Min(HuffmanTree tree,int k){
    int i=0;
    int min_weight=0;
    int min=0;
    while(tree[i].parent!=-1)
       i++;
    min_weight = tree[i].Weight;
    min = i;
    for(i; i < k; i++){
        if(tree[i].Weight<min_weight&&tree[i].parent==-1){
            min_weight = tree[i].Weight;
            min = i;
        }
    }
    tree[min].parent = 1;
    return min;
}
int SelectMin(HuffmanTree tree,int k,int *min1,int *min2){
    *min1=Min(tree,k);
    *min2=Min(tree,k);
    return -1;
}
HuffmanTree CreateHuffmanTree(HuffmanTree tree,int *weight,int total_indivual){
    int i = 0;
    int total=2 * total_indivual-1;
    tree=(HuffmanTree)malloc(total*sizeof(HufumanTreeNode));
    if(!tree)
       exit(0);
    for(i=0;i<total_indivual;i++){
        tree[i].Lchild=-1;
        tree[i].parent=-1;
        tree[i].Rchild=-1;
        tree[i].Weight=*weight;
        weight++;
    }
    for(i;i<total;i++){
        tree[i].Lchild=-1;
        tree[i].Rchild=-1;
        tree[i].parent=-1;
        tree[i].Weight=0;
    }

    int min1=0,min2=0;
    for(i=total_indivual;i<total;i++){
        SelectMin(tree,i,&min1,&min2);
        tree[min1].parent=i;
        tree[min2].parent=i;
        tree[i].Lchild=min1;
        tree[i].Rchild=min2;
        tree[i].Weight=tree[min1].Weight+tree[min2].Weight;
    }
    return tree;
}

int HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n){
    HC=(HuffmanCode)malloc(n*sizeof(char *));
    if(!HC)
       return -1;
    char *code;
    code=(char *)malloc(n*sizeof(char));
    if(!code)
       return -1;
    code[n-1]='\0';

    int i=0;
    for(i=0;i<n;i++){
        int current=i;
        int father=HT[i].parent;
        int start=n-1;
        while(father!=-1){
            if(current==HT[father].Lchild)
                code[--start]='0';
            else
                code[--start]='1';
            current=father;
            father=HT[father].parent;
        }
        HC[i]=(char *)malloc((n-start)*sizeof(char));
        if(!HC[i])
            return -1;
        strcpy(HC[i],code+start);
    }
    free(code);
    code=NULL;
    return -1;
}

int main(void){
    int total_individual=0,i=0;
    int *weight=(int *)malloc(total_individual*sizeof(int));
    printf("请输入要编码的字符个数:");
    scanf("%d",&total_individual);
    printf("请输入要编码的字符的权值\n:");
    for(i=0;i<total_individual;i++){
        scanf("%d",weight+i);
    }
    HuffmanTree tree;
    tree=CreateHuffmanTree(tree,weight,total_individual);

    HuffmanCode coding;
    HuffmanCoding(tree,coding,total_individual);
    for(i=0;i<total_individual;i++){
        puts(coding[i]);
    }
    free(weight);
    return -1;
}
